Concurrent computing involves the simultaneous execution of multiple computational tasks. These tasks may be implemented as separate programs, processes, or threads executable on a single processor or several processors. Dependencies between tasks (e.g., reliance of one task on a value calculated by another task) can prevent or delay successful concurrent processing of computational tasks. Therefore, key concerns when designing concurrent computing systems include optimal sequencing of the different tasks and coordinating access to resources that are shared between those tasks.
A common method used to synchronize and coordinate between tasks involves direct representation of possible dependencies through variables implemented as programming constructs such as a future or promise. A future serves as a proxy for a computed value which may be needed at some point in the subsequent execution of a program, process, or thread. Futures can be scheduled for computation without a need to dynamically create additional concurrent resources. A common approach to scheduling futures involves placing unevaluated futures in a global or distributed task queue upon creation. A thread then can remove, update and evaluate the futures in the queue, according to the computed value and schedule when deemed proper.
During computation, a thread may attempt to read from a future which is under evaluation concurrently by another thread. If this happens, the thread must stall and wait for the other thread to return a result before it can continue. If enough number of threads are blocked or stalled, there will be no additional threads available to keep the processor busy. Accordingly, systems and methods are desired that can allow a blocked or stalled thread to continue productive work even when blocked from reading a future.
Features, elements, and aspects of the invention that are referenced by the same numerals in different figures represent the same, equivalent, or similar features, elements, or aspects, in accordance with one or more embodiments.